<head>
    <meta charset="UTF-8">
<title>算法提高 Petri Net Simulation</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]-->
<p class="Default" style="text-indent:24.0pt;mso-char-indent-count:2.0"><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">一个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">网是一个计算模型，用来说明并发事件。每个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">网包含一些库所（被表示成圆圈），变迁（被表示成黑色的矩形），和一些有向边，用来连接库所到变迁，和变迁到库所。每个库所能够包含</span><span lang="EN-US">0</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个或多个令牌（被表示成黑点）。</span></p>
<p class="Default" style="text-indent:24.0pt;mso-char-indent-count:2.0"><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">这里有</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个例子：</span></p>
<p align="center" class="Default" style="text-align:center;text-indent:24.0pt;
mso-char-indent-count:2.0"><span lang="EN-US"> </span></p>
<p align="center" class="Default" style="text-align:center;text-indent:24.0pt;
mso-char-indent-count:2.0"><span lang="EN-US"><img width="319" height="222" alt="" src="http://lx.lanqiao.cn/RequireFile.do?fid=LnH26QFn" /> </span></p>
<p align="center" class="Default" style="text-align:center;text-indent:24.0pt;
mso-char-indent-count:2.0">&nbsp;</p>
<p align="center" class="Default" style="text-align:center;text-indent:24.0pt;
mso-char-indent-count:2.0"><span lang="EN-US"><img width="419" height="222" alt="" src="http://lx.lanqiao.cn/RequireFile.do?fid=3hAB8BDe" /></span></p>
<p class="Default" style="text-indent:24.0pt;mso-char-indent-count:2.0"><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">在上面的第一个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">网中，有</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">个库所（</span><span lang="EN-US">P1 </span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">和</span> <span lang="EN-US">P2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">）和</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个变迁（</span><span lang="EN-US">T1 </span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">和</span> <span lang="EN-US">T2</span><span style="font-family:宋体;mso-ascii-font-family:
SimSun;mso-hansi-font-family:SimSun">）。</span><span lang="EN-US">P1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">初始有</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个令牌。</span><span lang="EN-US">P2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">没有令牌。</span><span lang="EN-US">P1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">是变迁</span><span lang="EN-US">T1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">的输入库所，</span><span lang="EN-US">P2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">是</span><span lang="EN-US">T1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">的输出库所。在第二个例子中，有</span><span lang="EN-US">3</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个库所和</span><span lang="EN-US">3</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">个变迁，</span><span lang="EN-US">P1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">有</span><span lang="EN-US">3</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">个令牌。</span><span lang="EN-US">T2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">有</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">个输入库所，</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个都是</span><span lang="EN-US">P2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">。</span></p>
<p class="Default"><span lang="EN-US">&nbsp;</span></p>
<p class="Default"><span style="font-size:15.0pt;font-family:宋体;mso-ascii-font-family:
SimSun;mso-hansi-font-family:SimSun">一个</span><span lang="EN-US" style="font-size:15.0pt">Petri</span><span style="font-size:15.0pt;font-family:
宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">网的操作</span></p>
<p class="Default"><span lang="EN-US" style="font-size:15.0pt">&nbsp;</span></p>
<p class="Default" style="text-indent:24.0pt;mso-char-indent-count:2.0"><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">每个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">网的变迁要么被允许，要么不被允许。一个变迁被允许当且仅当每个输入库所都至少有</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个令牌。任何被允许的变迁可以发生。如果有多个变迁被允许，任何一个都可能发生。当一个变迁发生时，每个输入库所都会移除</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个令牌，每个输出库所都会增加</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">个令牌。这会有效地利用原子能来完成，作为一个事件。如果没有一个变迁被允许，这个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">网就被认为是死的。</span></p>
<p class="Default" style="text-indent:24.0pt;mso-char-indent-count:2.0"><span lang="EN-US">&nbsp;</span></p>
<p class="Default" style="text-indent:24.0pt"><span style="font-family:宋体;
mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">最上面那个例子，只有</span><span lang="EN-US">T1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">是被允许的。当它发生时，会从</span><span lang="EN-US">P1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">移除</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个令牌，给</span><span lang="EN-US">P2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">增加</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个令牌。然后</span><span lang="EN-US">T2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">就被允许了。当它发生时，会从</span><span lang="EN-US">P2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">移除</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">个令牌，给</span><span lang="EN-US">P1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">增加</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">个令牌。显然，这个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">网将会永远重复这个循环。</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">&nbsp;</span></p>
<p class="Default" style="text-indent:24.0pt"><span style="font-family:宋体;
mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">下面那个例子更加有趣。</span><span lang="EN-US">T1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">被允许然后发生，有效地移动</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">个令牌给</span><span lang="EN-US">P2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">。在这个时候，</span><span lang="EN-US">T1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">仍然是唯一被允许的变迁（</span><span lang="EN-US">T2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">被允许需要</span><span lang="EN-US">P2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">有</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个令牌）。</span><span lang="EN-US">T1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">再次发生，在</span><span lang="EN-US">P1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">剩下</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">个令牌，</span><span lang="EN-US">P2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">中有</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">个令牌。现在，</span><span lang="EN-US">T1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">和</span><span lang="EN-US">T2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">都被允许。假设</span><span lang="EN-US">T2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">发生，从</span><span lang="EN-US">P2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">移除</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个令牌，给</span><span lang="EN-US">P3</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">增加</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个令牌。现在</span><span lang="EN-US">T1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">和</span><span lang="EN-US">T3</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">都被允许。直到没有变迁被允许，你应该能看到在</span><span lang="EN-US">9</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">次变迁发生后，在</span><span lang="EN-US">P2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">仅留下</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">个令牌。（注意到，如果当</span><span lang="EN-US">T1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">和</span><span lang="EN-US">T2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">都被允许的时候，</span><span lang="EN-US">T1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">代替了</span><span lang="EN-US">T2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">发生，这个结果也同样是在</span><span lang="EN-US">9</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">次变迁发生后。）</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">&nbsp;</span></p>
<p class="Default" style="text-indent:24.0pt"><span style="font-family:宋体;
mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">在这个问题中，你将会被给出</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个或多个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">网的描述。对于每个描述，你将要模拟</span><span lang="EN-US">NF</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">（</span><span lang="EN-US">0 &lt; NF &lt; 1000</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">）次变迁的发生，然后输出留在库所里的令牌数量。如果这个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">网在</span><span lang="EN-US">NF</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">次变迁发生之前就死了，你将按事实输出。</span></p>
<!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:PunctuationKerning />
<w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>
<w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>
<w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery>
<w:ValidateAgainstSchemas />
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:Compatibility>
<w:SpaceForUL />
<w:BalanceSingleByteDoubleByteWidth />
<w:DoNotLeaveBackslashAlone />
<w:ULTrailSpace />
<w:DoNotExpandShiftReturn />
<w:AdjustLineHeightInTable />
<w:BreakWrappedTables />
<w:SnapToGridInCell />
<w:WrapTextWithPunct />
<w:UseAsianBreakRules />
<w:DontGrowAutofit />
<w:UseFELayout />
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
</w:WordDocument>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" LatentStyleCount="156">
</w:LatentStyles>
</xml><![endif]--><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:普通表格;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
</style>
<![endif]-->
<p><br />
【输入格式】</p>
<!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:PunctuationKerning />
<w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>
<w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>
<w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery>
<w:ValidateAgainstSchemas />
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:Compatibility>
<w:SpaceForUL />
<w:BalanceSingleByteDoubleByteWidth />
<w:DoNotLeaveBackslashAlone />
<w:ULTrailSpace />
<w:DoNotExpandShiftReturn />
<w:AdjustLineHeightInTable />
<w:BreakWrappedTables />
<w:SnapToGridInCell />
<w:WrapTextWithPunct />
<w:UseAsianBreakRules />
<w:DontGrowAutofit />
<w:UseFELayout />
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
</w:WordDocument>
</xml><![endif]-->
<p class="Default" style="text-indent:24.0pt"><span style="font-family:宋体;
mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">每个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">网的描述首先会包含一个整数</span><span lang="EN-US">NP</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">（</span><span lang="EN-US">0 &lt; NP &lt; 100</span><span style="font-family:宋体;mso-ascii-font-family:
SimSun;mso-hansi-font-family:SimSun">），紧接着有</span><span lang="EN-US">NP</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">个整数分别表示编号为</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">，</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">，</span><span lang="EN-US">&hellip;</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">，</span><span lang="EN-US">NP</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">的库所初始有多个个令牌。接着会有一个整数</span><span lang="EN-US">NT</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">（</span><span lang="EN-US">0 &lt; NT &lt; 100</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">）表示变迁的数量。然后，对于每个变迁（编号为</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">，</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">，</span><span lang="EN-US">&hellip;</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">，</span><span lang="EN-US">NT</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">）将会有一个以</span><span lang="EN-US">0</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">结尾的整数序列。序列中的负数代表输入库所，所以数字</span><span lang="EN-US">-n</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">代表有一个输入库所在</span><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">。序列中的正数代表输出库所，所以数字</span><span lang="EN-US">p</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">代表有一个输出库所在</span><span lang="EN-US">p</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">。每个库所至少有一个输入库所，至少有一个输出库所。最后，在</span><span lang="EN-US">NT</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个变迁的描述之后，会有一个整数代表你至多要模拟变迁发生的次数，</span><span lang="EN-US">NF</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">。输入会包含一个或多个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">网的描述，最后会有一个</span><span lang="EN-US">0</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">。</span></p>
<!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" LatentStyleCount="156">
</w:LatentStyles>
</xml><![endif]--><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:普通表格;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
</style>
<![endif]-->
<p><br />
【输出格式】</p>
<!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:PunctuationKerning />
<w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>
<w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>
<w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery>
<w:ValidateAgainstSchemas />
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:Compatibility>
<w:SpaceForUL />
<w:BalanceSingleByteDoubleByteWidth />
<w:DoNotLeaveBackslashAlone />
<w:ULTrailSpace />
<w:DoNotExpandShiftReturn />
<w:AdjustLineHeightInTable />
<w:BreakWrappedTables />
<w:SnapToGridInCell />
<w:WrapTextWithPunct />
<w:UseAsianBreakRules />
<w:DontGrowAutofit />
<w:UseFELayout />
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
</w:WordDocument>
</xml><![endif]-->
<p class="Default" style="text-indent:24.0pt"><span style="font-family:宋体;
mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">对于每个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">网的描述，输出三行。第一行输出是第几组数据（从</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">开始连续编号）和是否有</span><span lang="EN-US">NF</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">次变迁发生。如果有，输出这个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">网在</span><span lang="EN-US">NF</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">次变迁发生后仍然活着。否则输出这个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">网已经死了和变迁发生的次数。两种情况下，在第二行都输出在模拟结束后，包含</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个或多个令牌的库所的编号，和每个这种库所含有的令牌数量。输出的序列按编号递增。每组数据的第三行都应该是空行。</span><span lang="EN-US"> </span></p>
<p class="Default" style="text-indent:24.0pt"><span style="font-family:宋体;
mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">输入数据将会被选择来保证正确输出的唯一性。</span></p>
<p>【样例输入】</p>
<!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:PunctuationKerning />
<w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>
<w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>
<w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery>
<w:ValidateAgainstSchemas />
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:Compatibility>
<w:SpaceForUL />
<w:BalanceSingleByteDoubleByteWidth />
<w:DoNotLeaveBackslashAlone />
<w:ULTrailSpace />
<w:DoNotExpandShiftReturn />
<w:AdjustLineHeightInTable />
<w:BreakWrappedTables />
<w:SnapToGridInCell />
<w:WrapTextWithPunct />
<w:UseAsianBreakRules />
<w:DontGrowAutofit />
<w:UseFELayout />
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
</w:WordDocument>
</xml><![endif]-->
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">2</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">1 0</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">2</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">-1 2 0</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">-2 1 0</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">100</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">3</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">3 0 0</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">3</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">-1 2 0</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">-2 -2 3 0</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">-3 1 0</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">100</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">0</span></p>
<!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" LatentStyleCount="156">
</w:LatentStyles>
</xml><![endif]--><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:普通表格;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
</style>
<![endif]-->
<p><br />
【样例输出】</p>
<!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:PunctuationKerning />
<w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>
<w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>
<w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery>
<w:ValidateAgainstSchemas />
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:Compatibility>
<w:SpaceForUL />
<w:BalanceSingleByteDoubleByteWidth />
<w:DoNotLeaveBackslashAlone />
<w:ULTrailSpace />
<w:DoNotExpandShiftReturn />
<w:AdjustLineHeightInTable />
<w:BreakWrappedTables />
<w:SnapToGridInCell />
<w:WrapTextWithPunct />
<w:UseAsianBreakRules />
<w:DontGrowAutofit />
<w:UseFELayout />
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
</w:WordDocument>
</xml><![endif]-->
<p class="Default" style="text-indent:24.0pt;mso-char-indent-count:2.0"><span lang="EN-US">Case 1: still live after 100 transitions</span></p>
<p class="Default" style="text-indent:24.0pt;mso-char-indent-count:2.0"><span lang="EN-US">Places with tokens: 1 (1)</span></p>
<p class="Default"><span lang="EN-US">&nbsp;</span></p>
<p class="Default" style="text-indent:24.0pt;mso-char-indent-count:2.0"><span lang="EN-US">Case 2: dead after 9 transitions</span></p>
<p class="Default" style="text-indent:24.0pt;mso-char-indent-count:2.0"><span lang="EN-US">Places with tokens: 2 (1)</span></p>
<!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" LatentStyleCount="156">
</w:LatentStyles>
</xml><![endif]--><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:普通表格;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
</style>
<![endif]-->
<p><br />
【数据规模和约定】</p>
<!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:PunctuationKerning />
<w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>
<w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>
<w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery>
<w:ValidateAgainstSchemas />
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:Compatibility>
<w:SpaceForUL />
<w:BalanceSingleByteDoubleByteWidth />
<w:DoNotLeaveBackslashAlone />
<w:ULTrailSpace />
<w:DoNotExpandShiftReturn />
<w:AdjustLineHeightInTable />
<w:BreakWrappedTables />
<w:SnapToGridInCell />
<w:WrapTextWithPunct />
<w:UseAsianBreakRules />
<w:DontGrowAutofit />
<w:UseFELayout />
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
</w:WordDocument>
</xml><![endif]-->
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">0 &lt; NP &lt; 100</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">；</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">0 &lt; NT &lt; 100</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">；</span></p>
<p class="Default" style="text-indent:24.0pt"><span lang="EN-US">0 &lt; NF &lt; 1000</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:
SimSun">；</span></p>
<p class="Default" style="text-indent:24.0pt"><span style="font-family:宋体;
mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">每个库所初始的令牌数不超过</span><span lang="EN-US">10000</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">。</span></p>
<p class="Default" style="text-indent:24.0pt"><span style="font-family:宋体;
mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">每个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">网的所有变迁输入的整数序列的总长度不超过</span><span lang="EN-US">20000</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">。</span></p>
<p class="Default" style="text-indent:24.0pt"><span style="font-family:宋体;
mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">每个测试点包含不超过</span><span lang="EN-US">5</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;
mso-hansi-font-family:SimSun">个</span><span lang="EN-US">Petri</span><span style="font-family:宋体;mso-ascii-font-family:SimSun;mso-hansi-font-family:SimSun">网的描述。</span></p>
<!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" LatentStyleCount="156">
</w:LatentStyles>
</xml><![endif]--><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:普通表格;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
</style>
<![endif]-->